/**
 * cpu only, pthread
 * Baeza-Yates algorith with "new search algorithm"
 */


#include <common.h>
#include <pthread.h>


int4* input;
int4* end;
int4* idx1;
int4* invt;

//int4 items[MAX_KEY_NUM * 2];
//int4* lst;
pthread_mutex_t MUTEX;
int num_threads = 8;

/**
 * function declarations
 */
void init();
inline int find_mid(const int tag, int4* arr, int l, int h);
inline int intersection(int len1, int4* lst1, int len2, int4* lst2);
inline void intersection(int4 *a, int al, int ah, int4 *b, int bl, int bh, int *cnt);
inline void query(int len, const int4* keys, int4* lst);
void batch_query(int4* sss, int4* eee);
void *pthread_intersection(void *data);




int main(int argc, char *argv[])
{
	init();
	
	pthread_t *threads = (pthread_t *)malloc(sizeof(pthread_t) * num_threads);
	void *status;
	int rc;
	int i;

	
	pthread_mutex_init(&MUTEX, NULL);
	pthread_attr_t attr;
	pthread_attr_init(&attr);
	pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
	
	tv ts, te, tt;
	ts = get_time();
	
	for(i = 0; i < num_threads; i++)
	{
		rc = pthread_create(&threads[i], &attr, pthread_intersection, NULL);
		if(rc)
		{
			printf("Error; Failed to create #%d\n", rc);
		}
	}
	
	pthread_attr_destroy(&attr);
	
	for(i = 0; i < num_threads; i++)
	{
		pthread_join(threads[i], &status);
	}
	te = get_time();
	tt = time_diff(te, ts);
	
	printf("time: %ds and %dus\n", tt.tv_sec, tt.tv_usec);
	
	pthread_exit(NULL);
	return 0;
}

void *pthread_intersection(void *data)
{
	int4* lst = new int4[MAX_LIST_LEN];
	int4 items[MAX_KEY_NUM * 2];
	
	int4* ptr;
	while(1)
	{
		ptr = NULL;
		pthread_mutex_lock(&MUTEX);
		if(input < end)
		{
			ptr = input;
			input += ptr[0] + 1;
		}
		pthread_mutex_unlock(&MUTEX);
		if(ptr == NULL) break;
		
		// get query terms, and
		// perform list intersection
		int n = *ptr++;
		
		for(int i = 0; i < n; i++)
		{
			int id = *ptr++;
			items[i * 2] = idx1[id * 2];
			items[i * 2 + 1] = idx1[id * 2 + 1];
		}
		
		query(n, items, lst);
	}

	pthread_exit((void*) 0);
}

void init()
{
	input = (int4*) load_file(finput);
	idx1	= (int4*) load_file(fidx1);
	invt	= (int4*) load_file(finvt);
	
	end = input + get_file_size(finput) / sizeof(int4) * sizeof(byte1);
	//lst = new int4[MAX_LIST_LEN];
}

inline int intersection(int len1, int4* lst1, int len2, int4* lst2)
{
	int n = 0;
	int pos = 0;
	for(int i = 0; i < len1; i++)
	{
		pos = binary_search(lst1[i], lst2, pos, len2 - 1);
		if(pos >= 0)
			lst1[n++] = lst1[i];
		else
			pos = -pos - 1;	
	}
	
	return n;
}

inline int find_mid(const int tag, int4* arr, int l, int h)
{
	if(tag < arr[l]) return -l -1;
	if(tag > arr[h]) return -h - 1;
	int sp = (int)(1. * tag * h / arr[h]);
	//cout<<sp<<","<<tag<<","<<arr[l]<<","<<l<<endl;
	if(arr[sp] == tag) return sp;
	else if(tag < arr[sp])
		return bw_search(tag, arr, l, sp);
	else return fw_search(tag, arr, sp, h);
}

inline void intersection(int4 *a, int al, int ah, int4 *b, int bl, int bh, int *cnt)
{
	if(al > ah || bl > bh) return;

	int am = (al + ah) / 2, bml, bmr = -1;
	//int pos = binary_search(a[am], b, bl, bh);
	int pos = 0;
	if(bh - bl > 512)
		pos = find_mid(a[am], b, bl, bh);
	else
		pos = binary_search(a[am], b, bl, bh);
	int found = 1;

	// not found
	if(pos < 0)
	{
		pos = -pos - 1;
		found = 0;
		bmr = pos;
	}
	
	bml = pos - 1;
	if(bmr == -1)
		bmr = pos + 1;
	
	intersection(a, al, am - 1, b, bl, bml, cnt);
	
	// found
	if(found == 1)
	{
		a[*cnt] = a[am];
		(*cnt)++;
	}
	
	intersection(a, am + 1, ah, b, bmr, bh, cnt);
}

inline void query(int len, const int4* keys, int4* lst)
{
	for(int i = 0; i < keys[0]; i++)
	{
		lst[i] = *(invt + keys[1] + i);
	}
	
	
	int4 n = keys[0];

	for(int i = 1; i < len; i++)
	{
#define BaezaYates
#ifndef BaezaYates
		n = intersection(n, lst, keys[i * 2], invt + keys[i * 2 + 1]);
#else
		int results = 0;
		intersection(
			lst, 										0, n - 1, 
			invt + keys[i * 2 + 1], 0, keys[i * 2],
			&results);
			n = results;
#endif
	}
	
	/*cout<<"results: "<<n<<endl;
	for(int i = 0; i < n; i++)
	{
		cout<<lst[i]<<endl;
	}*/
}

/*void batch_query(int4* sss, int4* eee)
{
	while(sss < eee)
	//for(int i = 0; i < 2; i++)
	{
		int n = *sss;
		sss++;
		
		for(int i = 0; i < n; i++)
		{
			int id = *sss;
			sss++;
			items[i * 2] = idx1[id * 2];
			items[i * 2 + 1] = idx1[id * 2 + 1];
		}
		
		query(n, items);
		
		//break;
	}
}
*/

